977. Squares of a Sorted Array

解題程式碼

var sortedSquares = function (nums) {
  const out = [];
  let startP = 0;
  let endP = nums.length - 1;

  while (startP <= endP) {
    if (Math.pow(nums[startP], 2) > Math.pow(nums[endP], 2)) {
      out.push(Math.pow(nums[startP], 2));
      startP++;
    } else {
      out.push(Math.pow(nums[endP], 2));
      endP--;
    }
  }

  return out.reverse();
};

解題思路、演算法

設定兩個 pointer，分別向陣列頭尾兩邊遍歷，兩邊都平方，看哪邊大，加入到最終結果陣列，然後移動指針。

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(n)

參考資料

16. 3Sum Closest

解題程式碼

ar threeSumClosest = function(nums, target) {
    nums = nums.sort((a, b) => a - b);
    let sum = Infinity;

    for (let i = 0; i < nums.length; i++) {
        let leftP = i + 1;
        let rightP = nums.length - 1;

        while (leftP < rightP) {
            const tempSum = nums[i] + nums[leftP] + nums[rightP];
            if (tempSum > target) {
                rightP--;
            } else if (tempSum < target) {
                leftP++;

            } else {
                sum = tempSum;
                break;
            }
            if (Math.abs(tempSum - target) < Math.abs(sum - target)) {
                sum = tempSum;
            }
        }
    }

    return sum;
};

解題思路、演算法

思路和 3Sum 差不多。3Sum 的解題思路可參考之前發的文章。

解法的時間、空間複雜度

時間複雜度: O(n^2)
空間複雜度: O(1)

參考資料

435. Non-overlapping Intervals

解題程式碼

var eraseOverlapIntervals = function (intervals) {
  let counter = 0;
  intervals = intervals.sort((a, b) => a[0] - b[0]);
  let end = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= end) {
      // 當前區間頭和暫存區間尾巴沒有重疊
      end = intervals[i][1];
    } else {
      counter++;
      end = Math.min(end, intervals[i][1]);
    }
  }
  return counter;
};

解題思路、演算法

這題一樣先去做排序比較好處理，然後如果要找到需要移除的最少區間，那就是要盡量找到最小的 end 去和其他區間做比對。

所以假設有排序好的 intervals = [[1,2],[1,3],[2,3],[3,4]]，首先觀察 [1,2] 和 [1,3] 有重疊，會移除其中一個，並取最小的 end 並暫存，接下來若沒有重疊，就取下一個區間的 end 做暫存。

解法的時間、空間複雜度

時間複雜度: O(n * log n)
空間複雜度: O(1)

參考資料

Non-Overlapping Intervals - Leetcode 435 - Python

Leetcode 435. Non-overlapping Intervals